package 二叉排序树;

public class 二叉排序树 {
	public static void main(String[] args) {
		/*
		 *			7
		 *		  /	  \
		 *		 3	  10
		 *		/ \	  / \
		 *	   1   5 9  12
		 * 		\
		 * 		 2
		 */
		
		//创建树用的数组
		int arr[] = {7,3,10,12,5,1,9,2};
//		int arr[] = {7,3};
		//声明树
		BinarySortTree tree = new BinarySortTree();
		for(int i = 0; i < arr.length; i++) {
			tree.add(new Node(arr[i]));
		}
		//中序遍历
//		tree.midOrder();
		
		//查找删除结点
//		Node search = tree.search(3);
//		System.out.println(search);
		//查找删除结点父结点
//		Node parent = tree.searchParent(3);
//		System.out.println(parent);
		
		
		//特别注意删除时的情况，有多种情况考虑...
		//删除第一种情况：叶子结点
		System.out.println("---1---");
		tree.delNode(5);
		tree.midOrder();
		//删除第二种情况：有一个子树
		System.out.println("---2---");
		tree.delNode(1);
		tree.midOrder();
		//删除第三种情况：有两个子树
		System.out.println("---3---");
		tree.delNode(7);//就算删掉7(根)，也会保持二叉排序树
		tree.midOrder();
		
		
	}
}

/**
 * 二叉排序树
 * @author PC
 *
 */
class BinarySortTree {
	//根节点
	public Node root;
	
	/**
	 *  添加结点
	 * @param node
	 */
	public void add(Node node) {
		
		if(root == null) {
			//初始时根节点是空的，此时将第一个结点赋给根节点
			root = node;
		}else {
			//从根节点向后面一个一个添加
			root.add(node);
		}
	}
	
	/**
	 *  中序遍历
	 */
	public void midOrder() {
		if(root == null) {
			System.out.println("空树...");;
		}else {
			root.midOrder();
		}
	}
	
	/**
	 *  查找要删除结点
	 * @param value
	 */
	public Node search(int value) {
		if(root == null) {
			return null;
		}else {
			return root.search(value);
		}
	}
	
	/**
	 *  查找要删除结点的父结点
	 * @param value
	 */
	public Node searchParent(int value) {
		if(root == null) {
			return null;
		}else {
			return root.searchParent(value);
		}
	}
	
	/**
	 *  删除，分为三种情况
	 * @param value
	 */
	public void delNode(int value) {
		
		//待删除结点
		Node targetNode;
		//待删除结点父结点
		Node parent;
		if(root == null) {
			return;
		}else {
			//1、首先找到待删除结点
			targetNode = search(value);
			if(targetNode == null) {
				//没找到
				return;
			}
			//如果这棵树只有一个根节点
			if(root.left == null && root.right == null) {
				root = null;
				return;
			}
		}
		
		//2、找到待删除结点的父结点
		parent = searchParent(value);
		
		//3、判断删除时的三种情况
		//1)待删除结点是叶子结点
		if(targetNode.left == null && targetNode.right == null) {
			//判断targetNode是父结点的哪个孩子
			if(parent.left != null && parent.left.value == value) {
				//是左孩子
				parent.left = null;
			}else if(parent.right != null && parent.right.value == value) {
				//是右孩子
				parent.right = null;
			}
		}else if(targetNode.left != null && targetNode.right != null) {
			//3)待删除结点有两颗子树(子树包括两个结点)
			//3.1查找右子树里面最小结点
			int minVal = delRightTreeMin(targetNode.right);
			//3.2将最小节取出然后删除，替换到当前结点
			targetNode.value = minVal;
			
		}else {
			//2)待删除结点有一棵子树(一棵子树包括多个结点)
			//2.1如果待删除结点有左子结点
			if(targetNode.left != null) {
				//注意！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
				//并且待删除结点是根节点，且只有一个孩子，此时调用parent.left可能出错，如{7,3}
				if(parent != null) {
					//2.1.1如果待删除结点是左孩子
					if(parent.left.value == value) {
						parent.left = targetNode.left;
					}else {
						parent.right = targetNode.left;
					}
				}else {
					//arr={7,3}这种情况
					root = targetNode.left;
				}
			}else {
				//2.2如果待删除结点有右子结点
				//并且待删除结点是根节点，且只有一个孩子，此时调用parent.left可能出错，如{7,3}
				if(parent != null) {
					//2.2.1如果待删除结点是左孩子
					if(parent.left.value == value) {
						parent.left = targetNode.right;
					}else {
						parent.right = targetNode.right;
					}
				}else {
					//arr={7,3}这种情况
					root = targetNode.right;
				}
			}
		}
	}
	
	/**
	 *  找到以这个结点为根的树中最小结点，删除并返回
	 * @param node
	 * @return
	 */
	public int delRightTreeMin(Node node) {
		Node target = node;
		//向左找最小结点，就是最左边最后一个
		while(target.left != null) {
			target = target.left;
		}
		//删除这个最小结点，并返回
		delNode(target.value);
		return target.value;
		
	}
}

/**
 * 结点
 * @author PC
 *
 */
class Node{
	public int value;
	public Node left;
	public Node right;
	public Node(int value) {
		super();
		this.value = value;
	}
	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}
	
	/**
	 *  添加
	 * @param node
	 */
	public void add(Node node) {
		
		if(node == null) {
			return;
		}
		
		//不为空，判断传入结点大小，小在左，大在右
		if(node.value < this.value) {
			//当前结点大，新结点小，放左边
			if(this.left == null) {
				this.left = node;
			}else {
				//不为空，递归放到下一个结点左边
				this.left.add(node);
			}
		}else {
			//大于或等于都放右边
			if(this.right == null) {
				this.right = node;
			}else {
				this.right.add(node);
			}
		}
	}
	
	/**
	 *  中序遍历
	 */
	public void midOrder() {
		
		if(this.left != null) {
			this.left.midOrder();
		}
		System.out.println(this);
		if(this.right != null) {
			this.right.midOrder();
		}
	}
	
	/**
	 *  查找要删除的结点
	 * @param value
	 * @return
	 */
	public Node search(int value) {
		
		//如果当前结点就是要删除的结点，就返回，下面已经判断过null了
		if(this.value == value) {
			return this;
		}
		
		//如果要删除结点小于当前结点
		if(this.value > value) {
			if(this.left == null) {
				return null;
			}
			return this.left.search(value);
		}else {
			//大于或等于
			if(this.right == null) {
				return null;
			}
			return this.right.search(value);
		}
	}
	
	/**
	 *  查找要删除结点父结点
	 * @param value
	 * @return
	 */
	public Node searchParent(int value) {
		//如果当前结点是要删除的结点，就返回，注意一个父节点有两个子结点，都要判断
		if((this.left != null && this.left.value == value) 
				|| (this.right != null && this.right.value == value)) {
			return this;
		}
		
		//如果查找结点小于当前结点，向左递归找，并且左边不为空
		if(this.value > value && this.left != null) {
			//小于
			return this.left.searchParent(value);
		}else if(this.value <= value && this.right != null){
			//大于等于
			return this.right.searchParent(value);
		}else {
			//没找到
			return null;
		}
	}
}